home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / mint / utils / agrepsrc.zoo / main.c < prev    next >
C/C++ Source or Header  |  1993-01-19  |  36KB  |  1,032 lines
  1. /* Copyright (c) 1991 Sun Wu and Udi Manber.  All Rights Reserved. */
  2. #include "agrep.h"
  3. #include "checkfile.h"
  4.  
  5. unsigned Mask[MAXSYM];
  6. unsigned Init1, NO_ERR_MASK, Init[MaxError];
  7. unsigned Bit[WORD+1];
  8. CHAR buffer[BlockSize+Maxline+1];
  9. unsigned Next[MaxNext], Next1[MaxNext];
  10. unsigned wildmask, endposition, D_endpos; 
  11. int  REGEX, RE_ERR, FNAME, WHOLELINE, SIMPLEPATTERN;
  12. int  COUNT, HEAD, TAIL, LINENUM, INVERSE, I, S, DD, AND, SGREP, JUMP; 
  13. int  Num_Pat, PSIZE, num_of_matched, SILENT, BESTMATCH, NOUPPER;
  14. int  NOMATCH, TRUNCATE, FIRST_IN_RE, FIRSTOUTPUT;
  15. int  WORDBOUND, DELIMITER, D_length;
  16. int  EATFIRST, OUTTAIL;
  17. int  FILEOUT;
  18. int  DNA = 0;
  19. int  APPROX = 0;
  20. int  PAT_FILE = 0;
  21. int  CONSTANT = 0;
  22. int total_line = 0; /* used in mgrep */
  23.                                      
  24. CHAR **Textfiles;     /* array of filenames to be searched */
  25. CHAR old_D_pat[MaxDelimit] = "\n";  /* to hold original D_pattern */
  26. CHAR CurrentFileName[MAXNAME]; 
  27. CHAR Progname[MAXNAME]; 
  28. CHAR D_pattern[MaxDelimit] = "\n; "; /* string which delimits records --
  29.                                         defaults to newline */   
  30. int  NOFILENAME = 0,  /* Boolean flag, set for -h option */
  31.      FILENAMEONLY = 0,/* Boolean flag, set for -l option */
  32.      Numfiles = 0;    /* indicates how many files in Textfiles */
  33. extern int init();
  34. int table[WORD][WORD];
  35.  
  36. initial_value()
  37. {
  38.    int i; 
  39.  
  40.    JUMP = REGEX = FNAME = BESTMATCH = NOUPPER = 0;
  41.    COUNT = LINENUM = WHOLELINE = SGREP = 0;
  42.    EATFIRST = INVERSE = AND = TRUNCATE = OUTTAIL = 0; 
  43.    FIRST_IN_RE = NOMATCH = FIRSTOUTPUT = ON;
  44.    I = DD = S = 1;
  45.    HEAD = TAIL = ON;
  46.    D_length = 2;
  47.    SILENT = Num_Pat = PSIZE = SIMPLEPATTERN = num_of_matched = 0 ;
  48.    WORDBOUND = DELIMITER = RE_ERR = 0;
  49.    Bit[WORD] = 1;
  50.    for (i = WORD - 1; i > 0  ; i--)  Bit[i] = Bit[i+1] << 1; 
  51.    for (i=0; i< MAXSYM; i++) Mask[i] = 0;
  52. }
  53.  
  54. compute_next(M, Next, Next1)
  55. int M; unsigned *Next, *Next1;
  56. {
  57.   int i, j=0, n,  k, temp;
  58.   int mid, pp;
  59.   int MM, base;
  60.   unsigned V[WORD];
  61.    
  62.   base = WORD - M;
  63.   temp = Bit[base]; Bit[base] = 0;
  64.   for (i=0; i<WORD; i++) V[i] = 0;
  65.   for (i=1; i<M; i++)
  66.   {  
  67.       j=0;
  68.       while (table[i][j] > 0 && j < 10) {
  69.             V[i] = V[i] | Bit[base + table[i][j++]];
  70.       }
  71.   }
  72.   Bit[base]=temp;
  73.   if(M <= SHORTREG)
  74.   {
  75.     k = exponen(M);
  76.     pp = 2*k;
  77.     for(i=k; i<pp ; i++)
  78.     {   n = i;
  79.         Next[i]= (k>>1);
  80.         for(j=M; j>=1; j--)
  81.         {
  82.            if(n & Bit[WORD]) Next[i] = Next[i] | V[j];
  83.            n = (n>>1);
  84.         }
  85.     }      
  86.     return;
  87.   }
  88.   if(M > MAXREG) fprintf(stderr, "%s: regular expression too long\n", Progname);
  89.   MM = M;
  90.   if(M & 1) M=M+1;
  91.   k = exponen(M/2);
  92.   pp = 2*k;
  93.   mid = MM/2;
  94.   for(i=k; i<pp ; i++)
  95.   {     n = i;
  96.         Next[i]= (Bit[base]>>1);
  97.         for(j=MM; j>mid ; j--)
  98.         {
  99.            if(n & Bit[WORD]) Next[i] = Next[i] | V[j-mid];
  100.            n = (n>>1);
  101.         }
  102.         n=i-k;
  103.         Next1[i-k] = 0;
  104.         for(j = 0; j<mid; j++)
  105.         {
  106.            if(n & Bit[WORD]) Next1[i-k] = Next1[i-k] | V[MM-j];
  107.            n = (n>>1);
  108.         }
  109.   }      
  110.   return;
  111. }
  112.   
  113. exponen(m)
  114. int m;
  115. { int i, ex;
  116.   ex= 1;
  117.   for (i=0; i<m; i++) ex= ex*2;
  118.   return(ex);
  119. }
  120.  
  121. re1(Text, M, D)
  122. int Text, M, D;
  123. {
  124.   register unsigned i, c, r0, r1, r2, r3, CMask, Newline, Init0, r_NO_ERR; 
  125.   register unsigned end;
  126.   register unsigned hh, LL=0, k;  /* Lower part */
  127.   int  FIRST_TIME=ON, num_read , j=0, base;
  128.   unsigned A[MaxRerror+1], B[MaxRerror+1];
  129.   unsigned Next[MaxNext], Next1[MaxNext];
  130.   CHAR buffer[BlockSize+Maxline+1];
  131.   int FIRST_LOOP = 1;
  132.    
  133.   r_NO_ERR = NO_ERR_MASK;
  134.   if(M > 30) {
  135.      fprintf(stderr, "%s: regular expression too long\n", Progname);
  136.      exit(2);
  137.   }
  138.   base = WORD - M;
  139.   hh = M/2;
  140.   for(i=WORD, j=0; j < hh ; i--, j++) LL = LL | Bit[i];
  141.   if(FIRST_IN_RE) compute_next(M, Next, Next1); 
  142.                                    /*SUN: try: change to memory allocation */
  143.   FIRST_IN_RE = 0;
  144.   Newline = '\n';
  145.   Init[0] = Bit[base];
  146.   if(HEAD) Init[0] = Init[0] | Bit[base+1];
  147.   for(i=1; i<= D; i++) Init[i] = Init[i-1] | Next[Init[i-1]>>hh] | Next1[Init[i-1]&LL];
  148.   Init1 = Init[0] | 1; 
  149.   Init0 = Init[0];
  150.   r2 = r3 = Init[0];
  151.   for(k=0; k<= D; k++) { A[k] = B[k] = Init[k]; }
  152.   if ( D == 0 )
  153.   {
  154.     while ((num_read = read(Text, buffer + Maxline, BlockSize)) > 0)
  155.     {
  156.       i=Maxline; end = num_read + Maxline;
  157.       if((num_read < BlockSize) && buffer[end-1] != '\n') buffer[end] = '\n';
  158.       if(FIRST_LOOP) {         /* if first time in the loop add a newline */
  159.         buffer[i-1] = '\n';  /* in front the  text.  */
  160.     i--;
  161.         FIRST_LOOP = 0;
  162.       }
  163.       while ( i < end )
  164.       {
  165.         c = buffer[i++];
  166.         CMask = Mask[c];
  167.         if(c != Newline)
  168.         {  if(CMask != 0) {  
  169.               r1 = Init1 & r3;
  170.               r2 = ((Next[r3>>hh] | Next1[r3&LL]) & CMask) | r1;
  171.            }
  172.        else  {
  173.               r2 = r3 & Init1; 
  174.            }
  175.         }
  176.         else {  j++; 
  177.               r1 = Init1 & r3;            /* match against endofline */
  178.               r2 = ((Next[r3>>hh] | Next1[r3&LL]) & CMask) | r1;
  179.               if(TAIL) r2 = (Next[r2>>hh] | Next1[r2&LL]) | r2;                                        /* epsilon move */
  180.               if(( r2 & 1 ) ^ INVERSE) {
  181.                    if(FILENAMEONLY) {
  182.                           num_of_matched++;
  183.                           printf("%s\n", CurrentFileName);
  184.                           return;
  185.                    } 
  186.                    r_output(buffer, i-1, end, j);
  187.               }
  188.               r3 = Init0;
  189.               r2 = (Next[r3>>hh] | Next1[r3&LL]) & CMask | Init0;  
  190.                                                /* match begin of line */
  191.         }
  192.         c = buffer[i++];
  193.         CMask = Mask[c];
  194.         if(c != Newline)
  195.         {  if(CMask != 0) {  
  196.               r1 = Init1 & r2;
  197.               r3 = ((Next[r2>>hh] | Next1[r2&LL]) & CMask) | r1;
  198.            }
  199.        else   r3 = r2 & Init1; 
  200.         } /* if(NOT Newline) */
  201.         else {  j++;
  202.               r1 = Init1 & r2;            /* match against endofline */
  203.               r3 = ((Next[r2>>hh] | Next1[r2&LL]) & CMask) | r1;
  204.               if(TAIL) r3 = ( Next[r3>>hh] | Next1[r3&LL] ) | r3; 
  205.                                            /* epsilon move */
  206.               if(( r3 & 1 ) ^ INVERSE) {
  207.                    if(FILENAMEONLY) {
  208.                           num_of_matched++;
  209.                           printf("%s\n", CurrentFileName);
  210.                           return;
  211.                    } 
  212.                    r_output(buffer, i-1, end, j);
  213.               }
  214.               r2 = Init0;
  215.               r3 = ((Next[r2>>hh] | Next1[r2&LL]) & CMask) | Init0; 
  216.                    /* match begin of line */
  217.         }
  218.       } /* while i < end ... */
  219.       strncpy(buffer, buffer+num_read, Maxline);
  220.     } /* end while read()... */
  221.   return;
  222.   } /*  end if (D == 0) */
  223.   while ((num_read = read(Text, buffer + Maxline, BlockSize)) > 0)
  224.   {
  225.     i=Maxline; end = Maxline + num_read;
  226.     if((num_read < BlockSize) && buffer[end-1] != '\n') buffer[end] = '\n';
  227.     if(FIRST_TIME) {         /* if first time in the loop add a newline */
  228.         buffer[i-1] = '\n';  /* in front the  text.  */
  229.     i--;
  230.         FIRST_TIME = 0;
  231.     }
  232.     while (i < end )
  233.     {
  234.         c = buffer[i];
  235.         CMask = Mask[c];
  236.         if(c !=  Newline)
  237.         {
  238.            if(CMask != 0) {  
  239.               r2 = B[0];
  240.               r1 = Init1 & r2;
  241.               A[0] = ((Next[r2>>hh] | Next1[r2&LL]) & CMask) | r1;
  242.               r3 = B[1];
  243.               r1 = Init1 & r3;
  244.               r0 = r2 | A[0];     /* A[0] | B[0] */
  245.               A[1] = ((Next[r3>>hh] | Next1[r3&LL]) & CMask) |                                       (( r2 | Next[r0>>hh] | Next1[r0&LL])&r_NO_ERR) | r1 ;  
  246.                      if(D == 1) goto Nextchar;
  247.               r2 = B[2];
  248.               r1 = Init1 & r2;
  249.               r0 = r3 | A[1];
  250.               A[2] = ((Next[r2>>hh] | Next1[r2&LL]) & CMask) |